1. Field of the Invention
The present invention relates to a memory database, and more particularly, to a method of managing index data in a memory database, which efficiently stores and searches the index data by using a circular queue structure for indexing data in each node of a T-tree structure.
2. Discussion of the Related Art
In general, an indexing technique using a T-tree structure is often used for managing the index data in a main memory database. The main memory database uses a memory (i.e., D-RAM and S-RAM) instead of a disc for its storages. For example, a typical digital TV set uses the Electronic Program Guide (EPG) database system.
FIG. 1 illustrates a typical T-tree structure used for managing the index data in a main memory database system. As shown in FIG. 1, it includes many index nodes, each interconnected to its immediate upper and lower index nodes in a tree structure. Each index node has a limited space for storing its corresponding index information. Therefore, when a new set of information is added or one of existing information sets is deleted, each node creates a left lower node or a right lower node, and it transfers the corresponding information to the lower node created. The highest node in the tree structure shown in FIG. 1 is called as a root, and it transfers the information through a pointer, which is any one of a left lower node pointer and a right lower node pointer. The lower nodes corresponding to an upper node have the pointer information of the upper node.
FIG. 2 illustrates a typical construction of each node of the tree structure shown in FIG. 1 according to the related art. As it is shown in FIG. 2, an array technique is used to store the key value of each index node. Namely, the key values of an index node are initially stored in order. When an additional key value needs to be added, or when one of the stored key values needs to be deleted, all of the key values on the right of the key value being added or deleted must be rearranged, taking an extra processing time. For this reason, the systems, in which such additions and deletions of the key values frequently occurs, or the real-time main memory database systems have a lower data processing rate.